#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    stack<int> st;
    long long ans = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == '_') {
            if(st.size()) {
                ans += i - st.top();
                st.pop();
            }else{
                st.push(i);
            }
        }else if(s[i] == '('){
            st.push(i);
        } else{
            ans += i - st.top();
            st.pop();
        }
    }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while (t--)
        solve();
    return 0;
}